package cn.chen.数据结构.二叉树.平衡二叉树;

// 平衡二叉树
public class BalancedBinaryTree {

    AVLNode root;

    // 右旋转
    public void rightRotate(AVLNode node){

        if(node==null)
            return;

        AVLNode newNode=new AVLNode(node.value);

        // 将当前节点的右子树赋值给新节点的右子节点
        // 将当前节点的左子节点的右子节点赋值给新节点的左子节点
        // 将当前节点的左子节点的值赋值给当前节点
        // 将当前节点的左子节点的左子节点赋值给当前节点的左子节点
        // 将新节点赋值给当前节点的右子节点
        newNode.right=node.right;
        newNode.left= node.left.right;
        node.value=node.left.value;
        node.left=node.left.left;
        node.right=newNode;
    }
    // 左旋转
    /**
     * @param node  以该节点为根结点的树进行左旋转
     */
    public void leftRotate(AVLNode node){

        if(node==null)
            return;

        // 创建新节点。
        AVLNode newNode=new AVLNode(node.value);

        // 将新节点的左节点指向当前节点的左子节点
        newNode.left=node.left;

        // 将新节点的右节点指向当前节点的右子节点的左子节点
        newNode.right=node.right.left;

        // 将当前节点的右子树的值赋值给当前节点
        node.value=node.right.value;

        // 将当前节点的右子节点的右子节点设置为当前节点的右子节点
        node.right=node.right.right;

        // 将新节点设置为当前节点的左子节点
        node.left=newNode;
    }

    // 计算以当前节点为根结点的树的高度
    public int height(AVLNode node){

        // max方法就是返回两个参数中的最大的一个
        return Math.max(node.left==null?0:height(node.left),node.right==null?0:height(node.right))+1;   // 遍历到最底层，然后一层一层+1
    }

    // 插入节点的重载方法
    public void addNode(AVLNode node){

        if(node==null)
            return;
        if(root==null) {
            root = node;
            return;
        }
        addNode(root,node);

    }
    /**
     * @param rt    最开始是root（根结点），从root开始遍历，找到node插入的位置
     * @param node  要插入的节点
     */
    private void addNode(AVLNode rt, AVLNode node){

        if(node.value>=rt.value){  // 要插入的比当前节点的值大或等于，相同值放在右子树

            if(rt.right==null)  // 当前节点的右节点是否为空
                rt.right=node;
            else  // 不为空
                addNode(rt.right,node);
        }
        else{   // 要插入的比当前节点小，往左边放

            if(rt.left==null)
                rt.left=node;
            else
                addNode(rt.left,node);
        }
        // 执行到这里的时候已经插入完成了，从插入的位置到上上个位置，直到节点的两颗子树的高度差>1，就会执行下面的操作，进行旋转
        // 二叉排序树转成平衡二叉树（本质还是二叉排序树）
        doubleRotate(rt);       // 双旋转
    }
    // 双旋转，其实就是左旋转和右旋转进行结合

    /**
     * @param rt    需要进行平衡的两颗子树的父结点
     *
     * (2)左子树大于右子树：
     * ①当前节点的左子树的右子树大于当前节点的左子树的左子树：
     * 1)进行左旋转（以当前节点的左子树为根结点进行左旋转）。
     * ②然后进行右旋转（以当前节点为根结点进行右旋转）。
     * (3)右子树大于左子树：
     * ①当前节点的右子树的左子树大于当前节点的右子树的右子树：
     * 1)进行右旋转（以当前节点的右子树为根结点进行右旋转）。
     * ②然后进行左旋转（以当前节点为根结点进行左旋转）。
     */
    public void doubleRotate(AVLNode rt){

        if(rt.left!=null&&rt.right!=null){

            if(height(rt.right)-height(rt.left)>1) {// 左子树比右子树矮

                if(rt.right.left!=null
                        && (rt.right.right==null
                                || rt.right.right!=null&&height(rt.right.left)-height(rt.right.right)>0)){
                    // 当前节点的右子树的左子树大于当前节点的右子树的右子树：
                    rightRotate(rt.right);
                }
                leftRotate(rt);     // 不管上面条件是否满足，都会进行左旋转，因为右子树高于左子树
            }
            if(height(rt.left)-height(rt.right)>1) {// 左子树比右子树高

                if(rt.left.right!=null
                        && (rt.left.left==null
                                || rt.left.left!=null&&height(rt.left.right)-height(rt.left.left)>0)){
                    // 当前节点的左子树的右子树大于当前节点的左子树的左子树：
                    leftRotate(rt.left);
                }
                rightRotate(rt);    // 不管上面条件是否满足，都会进行右旋转，因为左子树比右子树高
            }
        }
    }

    // 中序遍历
    public void midOrder(){

        if(root==null){

            System.out.println("二叉排序树为空");
            return;
        }
        midOrder(root);
    }
    // 中序遍历二叉树
    private void midOrder(AVLNode node){

        if(node==null)
            return;

        midOrder(node.left);

        System.out.println(node);

        midOrder(node.right);
    }
}
